package org.lql.algo.codecrush.hot100.linked;

/**
 * @author: liangqinglong
 * @date: 2025-09-28 21:04
 * @description: 138. 随机链表的复制 <a href="https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class CopyRandomList {

	public static class Node {
		int val;
		Node next;
		Node random;

		public Node(int val) {
			this.val = val;
			this.next = null;
			this.random = null;
		}
	}

	public Node copyRandomList(Node head) {
		// 边界条件检查
		if (head == null) {
			return null;
		}
		// 遍历链表，为每个节点创建一个副本节点，并将副本节点插入到原节点之后
		Node current = head;
		while (current != null) {
			Node node = new Node(current.val);
			node.next = current.next;
			current.next = node;
			current = node.next;
		}

		// 遍历链表，设置副本节点的随机指针
		current = head;
		while (current != null) {
			if (current.random != null) {
				current.next.random = current.random.next;
			}
			current = current.next.next;
		}

		// 分离原链表和复制链表，并设置新链表的头节点
		Node oldList = head;
		Node newList = head.next;
		Node newHead = head.next;
		while (oldList != null) {
			oldList.next = oldList.next.next;
			if (newList.next != null) {
				newList.next = newList.next.next;
			}
			oldList = oldList.next;
			newList = newList.next;
		}
		return newHead;
	}

	public static void main(String[] args) {
		CopyRandomList copyRandomList = new CopyRandomList();
		Node node1 = new Node(7);
		Node node2 = new Node(13);
		Node node3 = new Node(11);
		Node node4 = new Node(10);
		Node node5 = new Node(1);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node1.random = null;
		node2.random = node1;
		node3.random = node5;
		node4.random = node3;
		node5.random = node1;
		Node newHead = copyRandomList.copyRandomList(node1);
		System.out.println(newHead);
	}
}
